\section{Analytical Model: Bit Budget Trade-offs}

We analyze and compare the different coherence directory schemes in order 
to understand their reasons for efficiency using an analytical model. 
In the following analysis, we assume that the total number
of cores in the system is $P$, i.e., $P$ private caches need to be kept
coherent and each cache has S sets and W ways. The total number of
%unique 
blocks that can be cached across all the L1 caches is
$P\times S \times W$.  
% ZHZ f not correct
%As we saw in Figure~\ref{max-patterns}, while the dominant
%access type is private, there is a significant fraction of blocks that
%are are shared between more than one processor. If $f$ the is the
%fraction of blocks shared between processors ($0\leq f \leq 1$), 
However, typically there are fewer unique blocks due to data sharing.
Assuming $f$ is the fraction of blocks that are unique in the total number 
of blocks ($0\leq f \leq 1$), then a coherence
directory essentially needs only $f*S*W*P$ entries to support
coherence operations.  Hence, the total bit budget for an
\textit{idealized directory} will be : $f * P * S *W *(T_b+P)$, where
$T_b$ is number of tag bits (typically 48 bits on a 64 bit
machine). For large multicores if $P>>T_b$, then the Ideal Directory
$= f*P*S*W*P$ and $\propto O(P^2)$. 

The shadow tags approach that completely replicates the L1 tags has a bit
budget as $P*S*W*T_b$, which is suited to the case when most cache lines
across the cores are private. 
%While in terms of storage overhead be
%better than an ideal directory, this 
Shadow tags has a smaller overhead than the ideal directory when all tags 
are unique ($f=1$), because the shadow tags do not
store the actual sharing patterns required by coherence. Every
coherence access needs a $W*P$-way search on $T_b$-bit tag fields. 
Even on small multicores, this is an energy-intensive associative search. 
Tagless Directory is built on the shadow tags approach. It adopts shadow
tags' approach of using the directory to represent the tags in the L1,
but unlike shadow tags, it only represents a summary of the tags in
each set using a bloom filter. Its overall budget is :
\begin{align*}
\text{Tagless Budget}  = S*B * H_n *  P \\[-0.8em]
 \intertext{B and $H_n$  are related based on false positives}\\[-2.5em] 
E[\mbox{False positives}] = (P-1) * (1 - (1-\frac{1}{B})^W)^{H_n} \\[-0.8em]
\intertext{B: Buckets/Hash function ; $H_n$ : \# of Hash functions}\\[-3.5em]
\end{align*}
%So tagless's overall space is O(P),  with large multicores P
%dominates the relation leading to significant overhead.
%\sys{}, improves over tagless by decoupling taglesss's relation to
%O(p) and relates it to the actual sharing patterns in the
%application. \sys\ allows the designer to carefully consider the
%application suite targetted and appropriately size the pattern
%table. If the pattern table stores $2^{I_p}$ then the tagless table
%itself grows $\propto O (I_p)$. Overall the benefit of SPACE is that
%while the pattern table grows with P, the tagless table itself grows
%log (pattern table size). Overall \sys\ performs better than tagless
%under the following conditions
% ZHZ clean up a little:
With a large number of cores, $P$ will
dominate the relation, resulting in significant area overhead.
\sys{} improves over Tagless by decoupling Tagless' relation to
$P$ and relates it to the actual sharing patterns in the
application. \sys\ allows the designer to carefully consider the
application suite targeted and appropriately size the pattern
table. If the pattern table stores $2^{I_p}$ patterns, then the Tagless table
needs $I_p$ bits per entry, which is smaller than $P$. 
Therefore, in \sys\ 
the pattern table grows linearly with $P$, but the Tagless table itself grows as
$log(\text{pattern table size})$. Overall, \sys\ performs better than Tagless
under the following conditions
\begin{align*}
[S*B*H_n*I_p \text{(Tagless Table)} + 2^{I_p}*P \text{(Pattern
Table)}] \\< S*B*H_n*P
\end{align*}
In many cases for large multicores $P>>I_p$, which implies that $(P-I_p)$ can 
be approximated as $P$, so the condition can be reduced to $2^{I_p} < S*B*H_n$.


